/*
快速排序：最快的排序算法O(NlogN)
*/

/*
输出两个数组的交集，且输出结果的每个元素一定是唯一的
*/

#include <stdio.h>
#include <stdlib.h>

// 用于快速查找是否包含某个元素的哈希表结构
typedef struct 
{
    int key;
    int val;
} HashMap;

// 哈希表的插入操作
void insert(HashMap* map, int key, int val, int* size) 
{
    for (int idx = 0; idx < *size; ++idx) 
    {
        if (map[idx].key == key) 
        {
            return; // 如果已存在则直接返回
        }
    }
    map[*size].key = key;
    map[*size].val = val;
    (*size)++;
}

// 计算数组的交集
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) 
{
    HashMap* map = (HashMap*)malloc(sizeof(HashMap) * (nums1Size > nums2Size ? nums1Size : nums2Size));
    int size = 0;

    // 构建哈希表
    for (int idx = 0; idx < nums1Size; ++idx) 
    {
        insert(map, nums1[idx], nums1[idx], &size);
    }

    // 查找交集
    int* result = (int*)malloc(sizeof(int) * (nums1Size < nums2Size ? nums1Size : nums2Size));
    int resultSize = 0;
    for (int idx = 0; idx < nums2Size; ++idx) 
    {
        for (int jdx = 0; jdx < size; ++jdx)
         {
            if (map[jdx].key == nums2[idx]) 
            {
                result[resultSize++] = map[jdx].key;
                break;
            }
        }
    }

    *returnSize = resultSize;
    free(map);
    return result;
}

int main() 
{
    int nums1[] = {1, 2, 2, 1};
    int nums2[] = {2, 2};
    int returnSize;
    int* result = intersection(nums1, 4, nums2, 2, &returnSize);

    printf("Intersection: [");
    for (int idx = 0; idx < returnSize; ++idx) 
    {
        printf("%d", result[idx]);
        if (idx < returnSize - 1) 
        {
            printf(", ");
        }
    }
    printf("]\n");

    free(result);
    return 0;
}


